package com.kevinkk.dp;

/**
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 *
 * DP 公式：F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 * 其中需要注意的是初始化，dp[0] 和 dp[1] 都是 ，因为可以直接从“下标为 0 或下标为 1 的台阶开始爬楼梯”
 */

public class MinCostClimbingStairs {
    class Solution {
        public int minCostClimbingStairs(int[] cost) {
            int length = cost.length;
            int[] dp = new int[length + 1];
            for (int i = 2; i <= length; i++) {
                dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
            }
            return dp[length];
        }
    }
}
